package logica;

import java.util.ArrayList;
import java.util.Collections;
import java.util.LinkedList;
import java.util.List;
import java.util.Queue;

public class BuscaEmLargura {

	private Arvore arvore;
	private Vertice objetivo;
	private Queue<Vertice> fila;
	private ArrayList<Vertice> visitados;
	private ArrayList<Vertice> caminho;

	public BuscaEmLargura(Arvore arvore, Vertice objetivo) {
		this.arvore = arvore;
		this.objetivo = objetivo;
		this.visitados = new ArrayList<Vertice>();
		this.caminho = new ArrayList<Vertice>();
		this.fila = new LinkedList<Vertice>();
	}

	public ArrayList<Vertice> getVisitados() {
		return visitados;
	}
	public ArrayList<Vertice> getCaminho() {
		return caminho;
	}

	public Queue<Vertice> getFila() {
		return fila;
	}

	public boolean buscar(Vertice origem) {
		//Adiciona o vertice origem e seus adjacentes a lista de vertices arvore
		arvore.adicionaVertice(origem);
		arvore.getAdjacentes(origem, true);
		//Vertice[] vertices = arvore.getVerticesIniciais();
		boolean encontrou = false;

		fila.add(origem);
		origem.setVisitado(true);
		visitados.add(origem);
		fila.add(origem);

		while (!fila.isEmpty()){
			if (encontrou)
				break;
			Vertice verticeDaVez = fila.poll();
			encontrou = verticeDaVez.equals(objetivo);
			if (encontrou){
				visitados.add(verticeDaVez);
				fila.add(verticeDaVez);
				break;
			}
			List<Vertice> adjacentesDoVertice = arvore.getAdjacentes(verticeDaVez, true);
			for (Vertice adj : adjacentesDoVertice) {
				encontrou = adj.equals(objetivo);
				if (encontrou){
					visitados.add(adj);
					fila.add(adj);
					break;
				}
				if (!adj.foiVisitado()){
					adj.setVisitado(true);
					visitados.add(adj);
					fila.add(adj);
				}
			}
		}

		//Caminho da busca
		Vertice ultimoVertice = visitados.get(visitados.size() - 1);
		preencheCaminho(ultimoVertice);

		return encontrou;
	}

	private void preencheCaminho(Vertice ultimoVertice) {
		int alturaDaArvore = ultimoVertice.getNivel();
		Vertice verticeNivelAtual = ultimoVertice;
		caminho.add(ultimoVertice);

		for(int i = alturaDaArvore; i >= 0; i--) {
			for (Vertice vert : arvore.getAdjacentes(verticeNivelAtual, false)) {
				if (vert.getNivel() == (verticeNivelAtual.getNivel() - 1)){
					caminho.add(vert);
					verticeNivelAtual = vert;
					break;
				}
			}
		}

		Collections.reverse(caminho);
	}

//	private List<Vertice> getVerticesDoNivel(int nivel) {
//		List<Vertice> verticesDoNivel = new ArrayList<Vertice>();
//		for (Vertice vertice : visitados) {
//			if (vertice.getNivel() == nivel){
//				verticesDoNivel.add(vertice);
//			}
//		}
//		return verticesDoNivel;
//	}
}
